Search results for "rectangle packing problem"
showing 2 items of 2 documents
Scheduling under the network of temporo-spatial proximity relationships
2017
We discuss and introduce to the schedulingeld a novel, qualitative optimization model - scheduling under the network of temporo-spatial proximity relationships.We introduce a half perimeter proximity measure as an objective of scheduling.We present and evaluate an incremental Sequence Pair neighborhood evaluation algorithm, applicable to both scheduling and rectangle packing problems in VLSI industry. In this paper, we discuss and introduce to the scheduling field a novel optimization objective - half perimeter proximity measure in scheduling under the network of temporo-spatial proximity relationships. The presented approach enables to qualitatively express various reasons of scheduling ce…
Handling precedence constraints in scheduling problems by the sequence pair representation
2015
In this paper, we show that sequence pair (SP) representation, primarily applied to the rectangle packing problems appearing in the VLSI industry, can be a solution representation of precedence constrained scheduling. We present three interpretations of sequence pair, which differ in complexity of schedule evaluation and size of a corresponding solution space. For each interpretation we construct an incremental precedence constrained SP neighborhood evaluation algorithm, computing feasibility of each solution in the insert neighborhood in an amortized constant time per examined solution, and prove the connectivity property of the considered neighborhoods. To compare proposed interpretations…